package 双端队列;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 设计循环双端队列
// 测试链接 : https://leetcode.cn/problems/design-circular-deque/
public class CircularDeque {
    class MyCircularDeque1{
        public Deque<Integer> queue = new LinkedList<>();
        public int limit, size;

        public MyCircularDeque1(int k) {
            limit = k;
            size = 0;
        }

        public boolean insertFront(int val){
            if(isFull()){
                return false;
            }else{
                queue.offerFirst(val);
                size++;
                return true;
            }
        }

        public boolean insertLast(int val){
            if(isFull()){
                return false;
            }else{
                queue.offerLast(val);
                size++;
                return true;
            }
        }

        public boolean deleteFront(){
            if(isEmpty()){
                return false;
            }else{
                queue.pollFirst();
                size--;
                return true;
            }
        }

        public boolean deleteLast(){
            if(isEmpty()){
                return false;
            }else{
                queue.pollLast();
                size--;
                return true;
            }
        }

        public int getFront(){
            if(isEmpty()){
                return -1;
            }else{
                return queue.peekFirst();
            }
        }

        public int getRear(){
            if(isEmpty()){
                return -1;
            }else{
                return queue.peekLast();
            }
        }

        public boolean isFull(){
            return size == limit;
        }

        public boolean isEmpty(){
            return size == 0;
        }
    }

    // 自己用数组实现，常数操作快，但是leetcode数据量太小了，看不出优势
    class MyCircularDeque2{
        public int[] dequeue;
        public int l, r, size, limit;

        public MyCircularDeque2(int k) {
            dequeue = new int[k];
            l = 0;
            r = 0;
            size = 0;
            limit = k;
        }

        public boolean insertFront(int val){
            if(isFull()){
                return false;
            }else{
                if(isEmpty()){
                    l = 0;
                    r = 0;
                    dequeue[0] = val;
                }else{
                    l = l == 0 ? limit-1 : (l-1);
                    dequeue[l] = val;
                }
                size++;
                return true;
            }
        }

        public boolean insertLast(int val){
            if(isFull()){
                return false;
            }else{
                if(isEmpty()){
                    r = l = 0;
                    dequeue[0] = val;
                }else{
                    r = r==limit-1 ? 0 : (r+1);
                    dequeue[r] = val;
                }
                size++;
                return true;
            }
        }

        public boolean deleteFront(){
            if(isEmpty()){
                return false;
            }else{
                l = l==limit-1 ? 0 : (l+1);
                size--;
                return true;
            }
        }

        public boolean deleteLast(){
            if(isEmpty()){
                return false;
            }else{
                r = r == 0 ? limit-1 : (r-1);
                size--;
                return true;
            }
        }

        public int getFront(){
            if(isEmpty()){
                return -1;
            }else{
                return dequeue[l];
            }
        }

        public int getRear(){
            if(isEmpty()){
                return -1;
            }else{
                return dequeue[r];
            }
        }

        public boolean isFull(){
            return size == limit;
        }

        public boolean isEmpty(){
            return size == 0;
        }
    }
}
